<?php
/** 
 * 
 *
 * @package api
 * @subpackage collections
 * @author $Author$
 * 
 * @version $Id: AbstractList.php 14 2006-11-28 22:05:19Z rdff3 $
 */
/**
 * 
 */
require_once( "lang/Object.php" );
require_once( "util/AbstractCollection.php" );
require_once( "util/List.php" );
require_once( "util/Iterator.php" );
require_once( "util/ListIterator.php" );
require_once( "lang/IndexOutOfBoundsException.php" );

/**
 * Class AbstractList
 *
 * This class provides a skeletal implementation of the List  interface to minimize the effort required to implement this 
 * interface backed by a "random access" data store (such as an array). For sequential access data (such as a linked list),
 * AbstractSequentialList should be used in preference to this class.
 * 
 * To implement an unmodifiable list, the programmer needs only to extend this class and provide implementations for the 
 * get(int index) and size() methods.
 * 
 * To implement a modifiable list, the programmer must additionally override the set(int index, Object element) method (which 
 * otherwise throws an UnsupportedOperationException. If the list is variable-size the programmer must additionally override 
 * the add(int index, Object element) and remove(int index) methods.
 * 
 * The programmer should generally provide a void (no argument) constructor, as per the recommendation 
 * in the Collection interface specification.
 * 
 * Unlike the other abstract collection implementations, the programmer does not have to provide an iterator implementation; 
 * the iterator and list iterator are implemented by this class, on top the "random access" methods: get(int index), 
 * set(int index, Object element), set(int index, Object element), add(int index, Object element) and remove(int index).
 *
 * The documentation for each non-abstract methods in this class describes its implementation in detail. Each of these methods 
 * may be overridden if the collection being implemented admits a more efficient implementation.
 * 
 * This class is a member of the PHP Collections Framework. 
 *
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id: AbstractList.php 14 2006-11-28 22:05:19Z rdff3 $
 */
abstract class AbstractList extends AbstractCollection implements Llist {
	
	/**
	 * @access protected
	 * @var int $modCount The number of times this list has been <i>structurally modified</i>.
	 */
	protected $modCount = 0;

	/**
	 * Sole constructor.  (For invocation by subclass constructors)
	 */
	public function __construct() {
		parent::__construct();
	}
	
	/**
	 * Inserts all of the elements in the specified collection into this list at the specified position (optional operation).
	 * 
	 * Inserts all of the elements in the specified collection into this list at the specified position (optional operation). 
	 * Shifts the element currently at that position (if any) and any subsequent elements to the right (increases their indices). 
	 * The new elements will appear in this list in the order that they are returned by the specified collection's iterator. The 
	 * behavior of this operation is unspecified if the specified collection is modified while the operation is in progress. (Note 
	 * that this will occur if the specified collection is this list, and it's nonempty.).
	 * 
	 * This implementation gets an iterator over the specified collection and iterates over it, inserting the elements obtained 
	 * from the iterator into this list at the appropriate position, one at a time, using add(int, Object). Many implementations 
	 * will override this method for efficiency.
	 *
	 * Note that this implementation throws an UnsupportedOperationException unless add(int, Object) is overridden. 
	 *
	 * @param int $index index at which to insert first element from the specified collection
	 * @param Collection $c elements to be inserted into this list.
	 * @returns boolean true if this list changed as a result of the call.
	 * @throws {@link UnsupportedOperationException} - if the {@link addAllAt} method is not supported by this list.
	 * @throws {@link ClassCastException} - if the class of one of elements of the specified collection prevents it from 
	 		being added to this list.
	 * @throws {@link NullPointerException} - if the specified collection contains one or more null elements and this list 
	 		does not support null elements, or if the specified collection is null.
	 * @throws {@link IllegalArgumentException} - if some aspect of one of elements of the specified collection prevents it 
	 		from being added to this list.
	 * @throws {@link IndexOutOfBoundsException} - if the index is out of range (index < 0 || index > size()).
	 */
	public function addAllAt( $index, Collection $c ) {
		if (is_null($c))
			throw new NullPointerException();
			
		$return_value = false;	
		$c_iterator = $c->iterator();
		while ($c_iterator->hasNext() ) {
			$next = $c_iterator->getNext();
			$this->addAt( $index++, $next );
			$return_value = true;
		}
		return $return_value;
	}
	
	/**
	 * Inserts the specified element at the specified position in this list (optional operation).
	 * 
	 * Inserts the specified element at the specified position in this list (optional operation). Shifts the element 
	 * currently at that position (if any) and any subsequent elements to the right (adds one to their indices).
	 *
	 * This implementation always throws an UnsupportedOperationException.
	 *
	 * @param int $index index at which the specified element is to be inserted.
	 * @param Object $o element to be inserted
	 * @throws {@link UnsupportedOperationException} - if the {@link add} method is not supported by this list.
	 * @throws {@link ClassCastException} - if the class of the specified element prevents it from being added to this list.
	 * @throws {@link NullPointerException} - if the specified element is null and this list does not support null elements.
	 * @throws {@link IllegalArgumentException} - if some aspect of the specified element prevents it from being added to this list.
	 * @throws {@link IndexOutOfBoundsException} - if the index is out of range (index < 0 || index > size()).
	 */
	public function addAt( $index, Object $o ) {
		throw new UnsupportedOperationException();
	}
	
	/**
	 *
	 * Returns the total number of times this list has been structurally modified.
	 *
	 * Structural modifications are those that change the size of the list, or otherwise perturb it in such a fashion that 
	 * iterations in progress may yield incorrect results.
	 *
	 * @return int the number of times this list has been structurally modified.
	 */
	public function getModCount() {
		return $this->modCount;
	}
		
	/**
	 * Returns the index in this list of the first occurrence of the specified element.
	 *
	 * Returns the index in this list of the first occurrence of the specified element, or -1 if this list does not 
	 * contain this element. More formally, returns the lowest index i such that (o==null ? get(i)==null : o.equals(get(i))), 
	 * or -1 if there is no such index.
	 *
	 * This implementation first gets a list iterator (with listCollectionIterator()). Then, it iterates over the list until the 
	 * specified element is found or the end of the list is reached.
	 *
	 * @param Object $o element to seach for.
	 * @returns int the index in this list of the first occurance of the specified element, or -1 if this list does not contain 
	 			this element.
	 * @throws {@link ClassCastException} - if the type of the specified element is incompatable with this list (optional).
	 * @throws {@link NullPointerException} - if the specified element is null and this list does not support null 
	 			elements (optional).
	 */
	public function indexOf( Object $o ) {
		$list_iterator = $this->listIterator();
		
		while ($list_iterator->hasNext() ) {
			$next = $iterator->getNext();
			if ($o->equals( $next ))
				return $iterator->nextIndex();
		}
		return -1;
	}
	
	/**
	 * Returns an iterator over the elements in this list in proper sequence.
	 *
	 * This implementation returns a straightforward implementation of the iterator interface, relying on the backing list's 
	 * size(), get(int), and remove(int) methods.
	 * 
	 * Note that the iterator returned by this method will throw an UnsupportedOperationException in response to its remove 
	 * method unless the list's remove(int) method is overridden.
	 * 
	 * This implementation can be made to throw runtime exceptions in the face of concurrent modification, as described in 
	 * the specification for the (protected) modCount field. 
	 *
	 * @return AbstractListCollectionIterator an iterator over the elements in this list in proper sequence.
	 */
	public function iterator() {
		return new AbstractList_Iterator( $this );
	}
	
	/**
	 * Returns the index in this list of the last occurrence of the specified element.
	 *
	 * Returns the index in this list of the last occurrence of the specified element, or -1 if this list does not 
	 * contain this element. More formally, returns the lowest index i such that (o==null ? get(i)==null : o.equals(get(i))), 
	 * or -1 if there is no such index.
	 * 
	 * This implementation first gets a list iterator that points to the end of the list (with listCollectionIterator(size())). Then, 
	 * it iterates backwards over the list until the specified element is found, or the beginning of the list is reached.
	 * 
	 * @param Object $o element to seach for.
	 * @returns int the index in this list of the last occurance of the specified element, or -1 if this list does not contain 
	 *		this element.
	 * @throws {@link ClassCastException} - if the type of the specified element is incompatable with this list (optional).
	 * @throws {@link NullPointerException} - if the specified element is null and this list does not support null 
	 *		elements (optional).
	 */
	public function lastIndexOf( Object $o ) {
		$list_iterator = $this->listIteratorAt( $this->size() );
		
		while ($list_iterator->hasPrevious() ) {
			$prev = $list_iterator->getPrevious();
			if ($o->equals( $prev ))
				return $iterator->previousIndex();
		}
		return -1;
	}
	
	/** 
	 * Returns a list iterator of the elements in this list (in proper sequence).
	 * @returns ListCollectionIterator a list iterator of the elements in this list (in proper sequence).
	 */
	public function listIterator() {
		return $this->listIteratorAt( 0 );
	}
	
	/** 
	 * Returns a list iterator of the elements in this list (in proper sequence), starting at the specified position in this list.
	 * 
	 * The specified index indicates the first element that would be returned by an initial call to the next method. An initial 
	 * call to the previous method would return the element with the specified index minus one.
	 *
	 * @param int $index index of first element to be returned from the list iterator (by a call to the next method).
	 * @returns ListCollectionIterator a list iterator of the elements in this list (in proper sequence), starting at the specified position 
	 * 		in this list.
	 * @throws {@link IndexOutOfBoundException} - if the index is out of range (index < 0 || index > size()).
	 */
	public function listIteratorAt( $index ) {
		if ($index < 0 or $index > $this->size())
			throw new IndexOutOfBoundsException();
			
		return new AbstractList_ListIterator( $index, $this );
	}
	
	/** 
	 * Removes the element at the specified position in this list (optional operation).
	 * 
	 * Removes the element at the specified position in this list (optional operation). Shifts any subsequent elements to the 
	 * left (subtracts one from their indices). Returns the element that was removed from the list.
	 *
	 * @param int $index the index of the element to be removed.
	 * @returns Object the element previously at the specified position.
	 * @throws {@link UnsupportedOperationException} - if the {@link removeAt} method is not supported by this list.
	 * @throws {@link IndexOutOfBoundException} - if the index is out of range (index < 0 || index > size()).
	 */
	public function removeAt( $index ) {
		throw new UnsupportedOperationException();
	}
	
	protected function removeRange( $from_index, $to_index ) {
		if ($from_index < 0 or $to_index > $this->size() )
			return new IndexOutOfBoundsException();
			
		$iterator = $this->listIteratorAt( $from_index - 1 );
		while( $iterator->hasNext() ) {
			$iterator->getNext();
			if ($from_index++ < $to_index)
				$iterator->remove();
			else 
				break;
		}
	}
	
	/** 
	 * Replaces the element at the specified position in this list with the specified element (optional operation).
	 *
	 * @param int $index the index of the element to replace.
	 * @param Object $o element to be stored at the specified position.
	 * @returns Object the element previously at the specified position.
	 * @throws {@link UnsupportedOperationException} - if the {@link removeAt} method is not supported by this list.
	 * @throws {@link ClassCastException} - if the class of the specified element prevents it from being added to this list.
	 * @throws {@link NullPointerException} - if the specified element is null and this list does not support null elements.
	 * @throws {@link IllegalArgumentException} - if some aspect of the specified element prevents it from being added to this list.
	 * @throws {@link IndexOutOfBoundException} - if the index is out of range (index < 0 || index > size()).
	 */
	public function set( $index, Object $o ) {
		throw new UnsupportedOperationException();
	}
	
	/** 
	 * Returns a view of the portion of this list between the specified fromIndex, inclusive, and toIndex, exclusive.
	 * 
	 * Returns a view of the portion of this list between the specified fromIndex, inclusive, and toIndex, exclusive. (If 
	 * fromIndex and toIndex are equal, the returned list is empty.) The returned list is backed by this list, so non-structural 
	 * changes in the returned list are reflected in this list, and vice-versa. The returned list supports all of the optional 
	 * list operations supported by this list.
	 *
	 * This method eliminates the need for explicit range operations (of the sort that commonly exist for arrays). Any operation 
	 * that expects a list can be used as a range operation by passing a subList view instead of a whole list. For example, the 
	 * following idiom removes a range of elements from a list:
	 * 
     * <li>list.subList(from, to).clear();</li>
	 * 
	 * Similar idioms may be constructed for indexOf and lastIndexOf, and all of the algorithms in the Collections class 
	 * can be applied to a subList.
	 * 
	 * The semantics of the list returned by this method become undefined if the backing list (i.e., this list) is structurally 
	 * modified in any way other than via the returned list. (Structural modifications are those that change the size of this 
	 * list, or otherwise perturb it in such a fashion that iterations in progress may yield incorrect results.) 
	 * 
	 * @param int $from_index low endpoint (inclusive) of the subList.
	 * @param int $to_index high endpoint (exclusive) of the subList.
	 * @returns List a view of the specified range within this list
	 * @throws {@link IndexOutOfBoundsException} - for an illegal endpoint index value (fromIndex < 0 || toIndex > size || 
	 *		fromIndex > toIndex).
	 */
	public function subList( $from_index, $to_index ) {
		if ($from_index < 0 or $to_index > $this->size() )
			return new IndexOutOfBoundsException();
	
		return new AbstractList_SubList( $from_index, $to_index, $this );
	}	
}

/**
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id: AbstractList.php 14 2006-11-28 22:05:19Z rdff3 $
 * @internal
 */
class AbstractList_Iterator implements CollectionIterator {
	protected $list;
	
	protected $current;
	protected $expected_modCount;
	
	protected $next_completed = false;
	protected $prev_completed = false;
	
	
	public function __construct( Llist $list ) {	
		$this->list = $list;
		$this->current = 0;
		$this->expected_modCount = $this->list->getModCount();
	}
	
	public function hasNext() {
		if ($this->expected_modCount != $this->list->getModCount() )
			throw new ConcurrentModificationException();
	
		return ($this->current < $this->list->size());
	}
	
	public function current() {
		return $this->list->get( $this->current );
	}
	public function key() {
		return $this->current;
	}
	public function valid() {
		if ($this->expected_modCount != $this->list->getModCount() )
			throw new ConcurrentModificationException();
	
		return ($this->current < $this->list->size());
	}
	public function rewind() {
		$this->current = 0;
	}
	
	public function next() {
		$this->current++;
	}
	
	public function getNext() {
		if ( !$this->hasNext() )
			throw new NoSuchElementException();
			
		$this->next_completed = true;
		$this->prev_completed = false;
	
		return $this->list->get( $this->current++ );
	}
	
	public function remove() {
		if ($this->expected_modCount != $this->list->getModCount() )
			throw new ConcurrentModificationException();
		
		if ($this->next_completed)
			$this->list->removeAt( --$this->current );
		else if ($this->prev_completed ) 
			$this->list->removeAt( $this->current );
		else
			throw new IllegalStateException();
			
		$this->next_completed = $this->prev_completed = false;
		$this->expected_modCount++;
	}
}

/**
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id: AbstractList.php 14 2006-11-28 22:05:19Z rdff3 $
 * @internal
 */
class AbstractList_ListIterator extends AbstractList_Iterator implements ListIterator {
	private $add_completed = false;
	private $remove_completed = false;
	
	public function __construct( $index, Llist $list ) {
		parent::__construct( $list );
		
		if ($index < 0 or $index > $list->size())
			throw new IndexOutOfBoundsException();
		
		$this->current = $index;
	}
	
	public function add( Object $o ) {
		if ($this->expected_modCount != $this->list->getModCount() )
			throw new ConcurrentModificationException();
			
		$this->list->addAt( $this->current++, $o );
		$this->expected_modCount++;
		$this->add_completed = true;
	}
		
	public function hasPrevious() {
		if ($this->expected_modCount != $this->list->getModCount() )
			throw new ConcurrentModificationException();
			
		return ($this->current > 0);
	}
	
	public function next() {
		$this->add_completed = $this->remove_completed = false;
		return parent::next();
	}
	
	
	public function nextIndex() {
		if ($this->expected_modCount != $this->list->getModCount() )
			throw new ConcurrentModificationException();
			
		return $this->current;
	}
	
	
	public function getPrevious() {
		if ( !$this->hasPrevious() )
			throw new NoSuchElementException();
			
		$this->next_completed = false;
		$this->prev_completed = true;	
		$this->add_completed = $this->remove_completed = false;
		
		return $this->list->get( --$this->current );
	}
	
	public function previousIndex() {
		if ($this->expected_modCount != $this->list->getModCount() )
			throw new ConcurrentModificationException();
			
		return $this->current - 1;
	}
	
	public function remove() {
		$this->remove_completed = true;
		parent::remove();
	}
	
	public function set( Object $o ) {
		if ($this->expected_modCount != $this->list->getModCount() )
			throw new ConcurrentModificationException();
		
		if ($this->add_completed == true or $this->remove_completed == true )
			throw new IllegalStateException();
		else if ($this->next_completed == false and $this->prev_completed == false)
			throw new IllegalStateException();
		else
			$this->list->set( $this->current - 1, $o );
	}
}

/**
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id: AbstractList.php 14 2006-11-28 22:05:19Z rdff3 $
 * @internal
 */
class AbstractList_SubList extends AbstractList {
	private $from_index;
	private $to_index;
	private $list;
	private $size;
	private $expected_modCount;
	
	public function __construct( $from_index, $to_index, Llist $list) {
		parent::__construct();
		
		if ($from_index < 0 or $to_index > $list->size())
			throw new IndexOutOfBoundsException();
	
		$this->list = $list;
		$this->from_index = $from_index;
		$this->to_index = $to_index;
		$this->size = $to_index - $from_index;
		$this->expected_modCount = $this->list->getModCount();
	}
	
	public function set( $index, Object $o) {
		if ($this->expected_modCount != $this->list->getModCount() )
			throw new ConcurrentModificationException();
		if ($index < $this->from_index or $index > $this->to_index)
			throw new IndexOutOfBoundsException();
			
		$this->list->set($index, $o);
	}
	public function get( $index ) {
		if ($this->expected_modCount != $this->list->getModCount() )
			throw new ConcurrentModificationException();
		if ($index < $this->from_index or $index > $this->to_index)
			throw new IndexOutOfBoundsException();
			
		$this->list->get( $index );
	}
	public function addAt( $index, Object $o ) {
		if ($this->expected_modCount != $this->list->getModCount() )
			throw new ConcurrentModificationException();
		if ($index < $this->from_index or $index > $this->to_index)
			throw new IndexOutOfBoundsException();
		
		$this->list->addAt( $index, $o );
		$this->size++;
	}
	public function addAll( Collection $c ) {
		if ($this->expected_modCount != $this->list->getModCount() )
			throw new ConcurrentModificationException();
			
		$this->size += $c->size();
		return $this->list->addAll( $this->size, $c );
	} 
	
	public function removeAt( $index )  {
		if ($this->expected_modCount != $this->list->getModCount() )
			throw new ConcurrentModificationException();
		if ($index < $this->from_index or $index > $this->to_index)
			throw new IndexOutOfBoundsException();
	
		$this->list->removeAt( $index );
		$this->size--;
	}
	public function addAllAt( $index, Collection $c ) {
		if ($this->expected_modCount != $this->list->getModCount() )
			throw new ConcurrentModificationException();
		if ($index < $this->from_index or $index > $this->to_index)
			throw new IndexOutOfBoundsException();
	
		$this->size += $c->size();
		$this->list->addAllAt( $index, $c );
	}
	public function removeRange( $from_index, $to_index ) {
		if ($this->expected_modCount != $this->list->getModCount() )
			throw new ConcurrentModificationException();
			
		if ($from_index < $this->from_index or $to_index > $this->to_index)
			throw new IndexOutOfBoundsException();
		
		$this->list->removeRange( $from_index, $to_index );
		$this->size -= $to_index - $from_index;
	}
	
	public function size() {
		if ($this->expected_modCount != $this->list->getModCount() )
			throw new ConcurrentModificationException();
			
		return $this->size;
	}
	
	public function iterator() {
		if ($this->expected_modCount != $this->list->getModCount() )
			throw new ConcurrentModificationException();
		if ($index < $this->from_index or $index > $this->to_index)
			throw new IndexOutOfBoundsException();
			
		return new AbstractList_SubListIterator( $this->from_index, $this->to_index, $this->from_index, $this );
	}
	public function listIterator() {
		if ($this->expected_modCount != $this->list->getModCount() )
			throw new ConcurrentModificationException();
		if ($index < $this->from_index or $index > $this->to_index)
			throw new IndexOutOfBoundsException();
			
		return new AbstractList_SubListIterator( $this->from_index, $this->to_index, $this->from_index, $this );
	}
	public function listIteratorAt( $index ) {
		if ($this->expected_modCount != $this->list->getModCount() )
			throw new ConcurrentModificationException();
		if ($index < $this->from_index or $index > $this->to_index)
			throw new IndexOutOfBoundsException();
			
		return new AbstractList_SubListIterator( $this->from_index, $this->to_index, $index, $this );
	}
}

/**
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id: AbstractList.php 14 2006-11-28 22:05:19Z rdff3 $
 * @internal
 */
class AbstractList_SubListIterator extends AbstractList_ListIterator {
	
	private $from_index;
	private $to_index;
	
	public function __construct( $from_index, $to_index, $index, Llist $list ) {
		$this->from_index = $from_index;
		$this->to_index = $to_index;
		parent::__construct( $from_index, $list );
	}
	
	public function hasNext() {
		return ($this->current < $this->from_index);
	}
	public function hasPrevious() {
		return ($this->current > $to_index);
	}
}

?>
